package engine.operators;

import its.model.environment.Environment;
import its.model.environment.crossroad.Crossroad;
import its.model.environment.crossroad.Program;
import its.opt.graphs.AcyclicOrientedGraph;
import its.opt.graphs.FrequencyDecisionGraph;
import its.opt.graphs.LabeledTreeNode;
import its.opt.graphs.LabeledTreeNodeType;
import its.opt.operators.MergeOperator;
import its.opt.operators.OperatorType;
import its.opt.structures.BOAParams;
import its.opt.structures.NodeListItem;
import its.util.RandomFactory;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;

import engine.BoaOperator;
import engine.BoaPopulation;
import engine.Population;
import engine.individuals.Individual;
import engine.individuals.ProgramedTrafficNetIndividual;
import engine.operators.metric.MetricUtils;

/**
 * Generates offspring in the BOA (constructs the network for the selected
 * strings, and then uses it to generate new strings)
 * 
 * @author rafal.hladyszowski@gmail.com
 * 
 * @param <T>
 *          T extends Individual&lt;Integer&gt;
 */
public class BOAOffspringGeneratorOperator<T extends Individual<Integer>>
		implements BoaOperator<T> {

	private static final Logger LOGGER = Logger.getLogger(BOAOffspringGeneratorOperator.class.getName());
	
	private static final double FIXED_THRESHOLD = 0.0d;

	/** Paramseters of the evolution */
	private final BOAParams params;

	private final MetricUtils metricUtil;

	/**
	 * Creates the operator that will take the population and return offspring of
	 * the individuals.
	 * 
	 */
	public BOAOffspringGeneratorOperator(BOAParams params) {

		this.params = params;
		this.metricUtil = new MetricUtils(2*params.N);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see engine.BoaOperator#apply(engine.BoaPopulation, java.util.List)
	 */
	@SuppressWarnings("unchecked")
	@Override
	public BoaPopulation<T> apply(
			BoaPopulation<T> selectedParentsPopulation,
			List<Population<T>> ignore) {

		int offspringPopulationSize = (int) (params.N * params.percentOffspring / 100.0);

		BoaPopulation<T> offspring = new BoaPopulation<T>(new ArrayList<T>(
				offspringPopulationSize), selectedParentsPopulation.getChromosomeSize());

		// initialize the network (to an empty network)
		AcyclicOrientedGraph G = new AcyclicOrientedGraph(selectedParentsPopulation
				.getChromosomeSize());

		FrequencyDecisionGraph<T>[] frequencyGraphs = new FrequencyDecisionGraph[selectedParentsPopulation
				.getChromosomeSize()];

		// initialize the frequency trees

		for (int k = 0; k < selectedParentsPopulation.getChromosomeSize(); k++)
		{
			frequencyGraphs[k] = new FrequencyDecisionGraph<T>(selectedParentsPopulation, k);
		}

		// construct the Bayesian network to model the selected set of parents

		constructTheNetwork(G, frequencyGraphs, selectedParentsPopulation);

		// log the model for this generation

    logModel(G,frequencyGraphs);

		// generate the new points

		offspring = generateNewInstances(G, frequencyGraphs, offspring,
				offspringPopulationSize);

		// delete the network

		// delete G;

		// delete the trees

		// for (k=0; k<parents.n; k++)
		// delete T[k];

		return offspring;
	}

	private void logModel(AcyclicOrientedGraph g,
			FrequencyDecisionGraph<T>[] frequencyGraphs) {
		
		if (LOGGER.isLoggable(Level.FINE)) {
			StringBuilder sb = new StringBuilder("Printing model of population\n");

			for (int i = 0; i < g.size(); i++) {
				sb.append(i);
				sb.append(":\n");
				sb.append(frequencyGraphs[i].toString());
			}

			LOGGER.fine(sb.toString());
		}
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see engine.Operator#apply(engine.Population)
	 */
	@Override
	public Population<T> apply(Population<T> population) {

		throw new UnsupportedOperationException(
				"Use engine.BoaOperator#apply(engine.BoaPopulation, java.util.List) instead.");

	}

	private BoaPopulation<T> generateNewInstances(AcyclicOrientedGraph G,
			FrequencyDecisionGraph<T>[] frequencyGraphs,
			BoaPopulation<T> offspringPopulation, int offspringPopulationSize) {

		int N;
		int n;
		// assign the helper variables

		N = offspringPopulationSize;
		n = offspringPopulation.getChromosomeSize();

		// allocate index for topological ordering

		int[] index = new int[n];

		// order the vertices topologically

		topologicalOrdering(G, index);

		// generate the new stuff

		for (int i = 0; i < N; i++) {
			offspringPopulation.addIndividual(generateInstance(G, index,
					frequencyGraphs));
		}

		// free memory

		// free(index);
		//
		// // get back
		//
		// return 0;

		return offspringPopulation;
	}

	/**
	 * @deprecated uwaga! ta metoda nie jest parametryzowalna!!!
	 * @param G
	 * @param index
	 * @param graph
	 * @return
	 */
	@Deprecated
	private T generateInstance(AcyclicOrientedGraph G, int[] index,
			FrequencyDecisionGraph<T>[] graph) {

		// assign the helper variables

		int n = G.size();

		// generate the stuff

//		T instance = (T) new BinaryVectorIndividual(n);
		
		Collection<Crossroad> crossRoads = Environment.getActiveEnvironment()
				.getAllCrossroads();
		
		Program[] archetypeProgramInstances = new Program[crossRoads.size()];
		
		{
			int i = 0;
			for (Crossroad crossroad : crossRoads)
			{
				archetypeProgramInstances[i++] = crossroad.getProgram().clone();
			}
		}
		
		T instance = (T) new ProgramedTrafficNetIndividual(archetypeProgramInstances);

		for (int i = 0; i < n; i++) {

			int position = index[i];
			graph[position].iteratorFollowInstanceFromRoot(instance);

			double p0 = graph[position].getIterator().distribution[0];
			double p1 = graph[position].getIterator().distribution[1];
			p0 = p0 / (p0 + p1);
			p1 = 1.0d - p0;

			int value = (RandomFactory.getNextDouble() < (p1 /*+ 0.01d*/)/*/(6.0-(double)(position%6))*/) ? 1 : 0;

			instance.set(position, value);
		}

		instance.heal();
		
		return instance;
	}

	/**
	 * orders the variables topologically (so that we get all the stuff right
	 * before we generate the new instances)
	 * 
	 * @param G
	 *          the network
	 * @param index
	 *          index containing the topological ordering of variables (output)
	 */
	private void topologicalOrdering(AcyclicOrientedGraph G, int[] index) {

		int i, j;
		int n;
		int numAdded;
		boolean[] added;
		int numParents;
		int[] parentList;
		boolean canAdd;

		// assign the helper variables

		n = G.size();

		// allocate memory for the added array

		added = new boolean[n];
		for (i = 0; i < n; i++)
			added[i] = false;

		// order

		numAdded = 0;
		while (numAdded < n) {
			for (i = 0; i < n; i++) {
				if (!added[i]) {
					canAdd = true;
					parentList = G.getParentList(i);
					numParents = G.getNumIn(i);
					for (j = 0; (j < numParents) && (canAdd); j++) {
						if (!added[parentList[j]]) {
							canAdd = false;
						}
					}

					if (canAdd) {
						index[numAdded] = i;
						numAdded++;
						added[i] = true;
					}
				}
			}
		}
	}

	/**
	 * constructs a network given the population (including the decision graphs
	 * containing needed frequencies and the network itself needed in fact only
	 * for topological ordering of the variables
	 * 
	 * @param G
	 * @param freqDecisionGraph
	 * @param P
	 */
	private void constructTheNetwork(AcyclicOrientedGraph G,
			FrequencyDecisionGraph<T>[] freqDecisionGraph, BoaPopulation<T> P) {

		LOGGER.info("Metric compute");
		
		int n;
		int N;
		int maxIncoming;
		MergeOperator[][] merge;
		int[] numMerges;

		long operatorsLeft;

		// no operators applied

		// /! numAppliedSplits=numAppliedMerges=0;
		// /! maxDepth=0;

		// set the helper variables

		N = P.size();
		n = P.getChromosomeSize();
		maxIncoming = params.maxIncoming;

		// allocate all needed parameters

		// allocate the operators for each node
		its.opt.operators.Operator[] bestNodeOperator = new its.opt.operators.Operator[n];
		for (int i = 0; i < n; i++) {
			bestNodeOperator[i] = new its.opt.operators.Operator();
		}

		// we'll allocate some memory for the info on merge operators
		numMerges = new int[n];
		merge = new MergeOperator[n][];
		for (int i = 0; i < n; i++) {
			merge[i] = null;
			numMerges[i] = 0;
		}

		// remove all edges (just in case...)
		G.removeAllEdges();

		// ---- reset all needed parameters


		// no best operator at the moment
		its.opt.operators.Operator bestOperator = new its.opt.operators.Operator();

		// allocate and recompute the gains
		for (int i = 0; i < n; i++) {
			LabeledTreeNode treeNode = freqDecisionGraph[i].getLeaves().nodeValue;
			treeNode.gains = new double[n];
			treeNode.rightValue0Array = new double[G.size()];
			treeNode.rightValue1Array = new double[G.size()];
			treeNode.leftValue0Array = new double[G.size()];
			treeNode.leftValue1Array = new double[G.size()];
			recomputeDecisionGraphSplitGains(
					freqDecisionGraph[i],
					treeNode,
					G,
					maxIncoming,
					i,
					n,
					N);
			updateBestNodeOperator(
					bestNodeOperator[i],
					freqDecisionGraph[i],
					merge[i],
					numMerges[i],
					i,
					n);

			if (bestNodeOperator[i].compareTo(bestOperator) > 0) {
				bestOperator.updateTo(bestNodeOperator[i]);
			}
		}

		// all operators are left now, we can split in each node once on any
		// variable
		operatorsLeft = n * n;

		// while we gained and can do some more do splits
		while (bestOperator.gain > FIXED_THRESHOLD 
				&& operatorsLeft-- > 0) {

			if (operatorApplicable(bestOperator, G)) {
				// apply the operator

				applyOperator(bestOperator, G);

				LOGGER.info("Metric gain: " + bestOperator.gain + " adding edge: ("
						+ bestOperator.label + ", " + bestOperator.where + ")");
				
				// update the gains
				updateGainsAfterOperator(bestOperator, G, maxIncoming, N);

				// merge will be processed separately (if used at all)
				if (params.allowMerge) {
					numMerges[bestOperator.where] = recomputeDecisionGraphMergeGains(
							freqDecisionGraph[bestOperator.where], merge, bestOperator.where, N);
				}
			} else {
				// delete the operator (we can't apply it for some reason)
				deleteOperator(bestOperator);
			}

			// update the best operator in the node we've touched
			updateBestNodeOperator(bestNodeOperator[bestOperator.where],
					freqDecisionGraph[bestOperator.where], merge[bestOperator.where],
					numMerges[bestOperator.where], bestOperator.where, n);

			// everything alright, now we must get the best gain again
			bestOperator.reset();

			for (int i = 0; i < n; i++) {
				if (bestNodeOperator[i].compareTo(bestOperator) > 0) {
					bestOperator.updateTo(bestNodeOperator[i]);
				}
			}
		}

	}

	/**
	 * deletes an operator (just sets its gain to -1) - but this works not on
	 * merges, but splits
	 * 
	 * @deprecated refaktor {@link its.opt.operators.Operator}
	 * @param operator
	 */
	@Deprecated
	private void deleteOperator(its.opt.operators.Operator operator) {

		if (operator.type == OperatorType.OPERATOR_SPLIT_NODE) {
			operator.node.gains[operator.label] = -1;
		}

	}

	/**
	 * @deprecated wyglada jak refaktor do {@link FrequencyDecisionGraph}
	 * @param t
	 * @param merge
	 * @param node
	 * @param N
	 * @return
	 */
	@Deprecated
	private int recomputeDecisionGraphMergeGains(FrequencyDecisionGraph<T> t,
			MergeOperator[][] merge, int node, int N) {

		double scoreBefore;
		double scoreAfter;
		double gain;
		LabeledTreeNode dummy;
		NodeListItem a, b;
		int numLeaves;

		// allocate a dummy node

		dummy = new LabeledTreeNode(LabeledTreeNodeType.LEAF);

		// assign helper variables

		numLeaves = t.getNumLeaves();

		// allocate the merge operator array

		// if (merge[node]!=null)
		// merge[node] = null;

		merge[node] = new MergeOperator[numLeaves * (numLeaves + 1) / 2];
		int numMerges = 0;

		// compute merge gains for all pair of nodes

		for (a = t.getLeaves(); a.next != null; a = a.next)
			for (b = a.next; b != null; b = b.next) {
				// compute the score before the merge

				scoreBefore = nodeContribution(a.nodeValue, N) + nodeContribution(b.nodeValue, N);

				// update the dummy node (its frequencies are equal the sum of the
				// frequencies
				// of the two merged nodes)

				dummy.distribution[0] = a.nodeValue.distribution[0] + b.nodeValue.distribution[0];
				dummy.distribution[1] = a.nodeValue.distribution[1] + b.nodeValue.distribution[1];

				// compute the score after the merge (without really having to do the
				// merge)

				scoreAfter = nodeContribution(dummy, N);

				// compute the gain

				gain = scoreAfter - scoreBefore + Math.log(N) / Math.log(2.0d)
						/ 2;

				if (gain > 0) {
					// compute the score after the merge

					merge[node][numMerges] = new MergeOperator(gain, a.nodeValue, b.nodeValue);

					numMerges++;
				}
			}

		return numMerges;
	}

	/**
	 * updates gains after applying an operator to the network
	 * 
	 * @deprecated refaktor do {@link FrequencyDecisionGraph}
	 * @param operator
	 * @param graph
	 * @param maxParents
	 * @param N
	 */
	@Deprecated
	private void updateGainsAfterOperator(
			its.opt.operators.Operator operator,
			AcyclicOrientedGraph graph, 
			int maxParents,
			int N) {

		switch (operator.type) {
		case OPERATOR_SPLIT_NODE:
			recomputeDecisionGraphSplitGains(operator.decisionGraph, operator.node.left, graph, maxParents,
					operator.where, graph.size(), N);
			recomputeDecisionGraphSplitGains(operator.decisionGraph, operator.node.right, graph, maxParents,
					operator.where, graph.size(), N);
			break;

		case OPERATOR_MERGE_NODE:
			recomputeDecisionGraphSplitGains(operator.decisionGraph, operator.node, graph, maxParents, operator.where,
					graph.size(), N);
			break;

		default:
			throw new IllegalArgumentException(
					"ERROR: Operator not defined (updateGainsAfterOperator)! Exiting!");
		}
	}

	/**
	 * applies the operator to a Bayesian network with decision graphs
	 * 
	 * @deprecated refaktor do {@link AcyclicOrientedGraph}
	 * @param operator
	 * @param graph
	 */
	@Deprecated
	private void applyOperator(
			its.opt.operators.Operator operator,
			AcyclicOrientedGraph graph) {

		// apply the operator

		switch (operator.type) {
		case OPERATOR_SPLIT_NODE:
			operator.decisionGraph.split(operator.node, operator.label);
			operator.node.left.gains = new double[graph.size()];
			operator.node.left.rightValue0Array = new double[graph.size()];
			operator.node.left.rightValue1Array = new double[graph.size()];
			operator.node.left.leftValue0Array = new double[graph.size()];
			operator.node.left.leftValue1Array = new double[graph.size()];
			operator.node.right.gains = new double[graph.size()];
			operator.node.right.rightValue0Array = new double[graph.size()];
			operator.node.right.rightValue1Array = new double[graph.size()];
			operator.node.right.leftValue0Array = new double[graph.size()];
			operator.node.right.leftValue1Array = new double[graph.size()];
			operator.node.left.distribution[0] = operator.node.leftValue0Array[operator.label];
			operator.node.left.distribution[1] = operator.node.leftValue1Array[operator.label];
			operator.node.right.distribution[0] = operator.node.rightValue0Array[operator.label];
			operator.node.right.distribution[1] = operator.node.rightValue1Array[operator.label];
			// /! if (x.node.depth+1>getMaxDepth())
			// /! setMaxDepth(x.node.depth+1);
			graph.addEdge(operator.label, operator.where);
			// /!numAppliedSplits++;
			break;

		case OPERATOR_MERGE_NODE:
			operator.decisionGraph.merge(operator.node, operator.node2);
			// /!numAppliedMerges++;
			break;

		default:
			throw new IllegalArgumentException(
					"ERROR: Operator not defined (applyOperator)! Exiting!");
		}
	}

	/**
	 * @deprecated refaktor do {@link AcyclicOrientedGraph}
	 * @param operator
	 * @param g
	 * @return
	 */
	@Deprecated
	private boolean operatorApplicable(
			its.opt.operators.Operator operator,
			AcyclicOrientedGraph g) {

		// we can split only when we can add a parent or it's already there

		if (operator.type == OperatorType.OPERATOR_SPLIT_NODE) {
			return ((g.connected(operator.label, operator.where)) || (g
					.canAddEdge(operator.label, operator.where)));
		} else if (operator.type == OperatorType.OPERATOR_MERGE_NODE) {
			return true;
		}

		// get back

		return false;
	}

	/**
	 * @deprecated refaktor do {@link its.opt.operators.Operator}
	 * @param maxGainOperator
	 * @param freqDecisionGraph
	 * @param merge
	 * @param numMerges
	 * @param node
	 * @param n
	 * @return
	 */
	@Deprecated
	private void updateBestNodeOperator(its.opt.operators.Operator maxGainOperator,
			FrequencyDecisionGraph<T> freqDecisionGraph, MergeOperator[] merge, int numMerges, int node,
			int n) {

		// printf("Updating best gain for node %u (%u +
		// %u)\n",node,t.getNumLeaves(),numMerges);

		// assign some helper variables

		int numLeaves = freqDecisionGraph.getNumLeaves();

		// reset the operator

		maxGainOperator.reset();

		// try all splits, and update the best oeprator for this node

		NodeListItem leafItem = freqDecisionGraph.getLeaves();
		for (int i = 0; i < numLeaves; i++, leafItem = leafItem.next) {
			for (int j = 0; j < n; j++) {
				if (maxGainOperator.gain < leafItem.nodeValue.gains[j]) {
					maxGainOperator.gain = leafItem.nodeValue.gains[j];
					maxGainOperator.type = OperatorType.OPERATOR_SPLIT_NODE;
					maxGainOperator.where = node;
					maxGainOperator.label = j;
					maxGainOperator.node = leafItem.nodeValue;
					maxGainOperator.node2 = null;
					maxGainOperator.decisionGraph = freqDecisionGraph;
				}
			}
		}

		// try all merges

		for (int i = 0; i < numMerges; i++) {
			if (merge[i].gain > maxGainOperator.gain) {
				maxGainOperator.gain = merge[i].gain;
				maxGainOperator.type = OperatorType.OPERATOR_MERGE_NODE;
				maxGainOperator.where = node;
				maxGainOperator.label = 0;
				maxGainOperator.node = merge[i].a;
				maxGainOperator.node2 = merge[i].b;
				maxGainOperator.decisionGraph = freqDecisionGraph;
			}
		}
	}

	/**
	 * @deprecated refaktor do {@link FrequencyDecisionGraph}
	 * @param freqDecisionGraph
	 * @param treeNode
	 * @param G
	 * @param maxParents
	 * @param node
	 * @param n
	 * @param N
	 */
	@Deprecated
	private void recomputeDecisionGraphSplitGains(
			FrequencyDecisionGraph<T> freqDecisionGraph,
			LabeledTreeNode treeNode, 
			AcyclicOrientedGraph G,
			int maxParents,
			int node,
			int n,
			int N)
	{
		int label;
		double scoreBefore;
		double scoreAfter;
		double gain;
		LabeledTreeNode dummy;
		double[] leftValue0, leftValue1;
		double[] rightValue0, rightValue1;
		double leftContribution;
		double rightContribution;

		// if this bit fixed now, ignore it

		if ((treeNode.distribution[0] <= FIXED_THRESHOLD) || (treeNode.distribution[1] <= FIXED_THRESHOLD)) {
			for (label = 0; label < n; label++) {
				treeNode.gains[label] = -1;
			}
			return;
		}

		// depth is too big - we can't split

		if (treeNode.depth >= maxParents) {
			for (label = 0; label < n; label++) {
				treeNode.gains[label] = -1;
			}
			return;
		}

		// compute basic contribution of this node (before split)

		scoreBefore = nodeContribution(treeNode, N);

		// allocate memory for the frequencies of the splits

		leftValue0 = new double[n];
		leftValue1 = new double[n];
		rightValue0 = new double[n];
		rightValue1 = new double[n];

		// try all splits we can do (must not be our parent, and must not
		// create a cycle)

		freqDecisionGraph.computeSplitFrequencies(
				treeNode, 
				leftValue0, 
				leftValue1, 
				rightValue0,
				rightValue1);

		// we'll need this dummy node

		dummy = new LabeledTreeNode(LabeledTreeNodeType.LEAF);

		for (label = 0; label < n; label++) {
			if (node != label
					&& treeNode.parentLabelCoincidenceVector[label] == 0
					&& (G.connected(label, node) 
							|| (G.getNumIn(node) < maxParents 
									&& G.canAddEdge(label, node)))) {
				// compute frequencies if we did split

				dummy.distribution[0] = leftValue0[label];
				dummy.distribution[1] = leftValue1[label];
				leftContribution = nodeContribution(dummy, N);

				dummy.distribution[0] = rightValue0[label];
				dummy.distribution[1] = rightValue1[label];
				rightContribution = nodeContribution(dummy, N);

				// new contribution

				scoreAfter = leftContribution + rightContribution;

				// compute the gain

				gain = scoreAfter - scoreBefore - Math.log(N) / Math.log(2.0d)
						/ 2; // plus 1 leaf (-0.5 log_2 N per leaf) to score

				// update the contribution

				treeNode.gains[label] = gain;

				// update the values we computed (for future reference)

				treeNode.rightValue0Array[label] = rightValue0[label];
				treeNode.rightValue1Array[label] = rightValue1[label];
				treeNode.leftValue0Array[label]  = leftValue0[label];
				treeNode.leftValue1Array[label]  = leftValue1[label];
			} else {
				treeNode.gains[label] = -1;
			}
		}

	}

	/**
	 * @deprecated refaktor do {@link LabeledTreeNode}
	 * @param treeNode
	 * @param N
	 * @return
	 */
	@Deprecated
	private double nodeContribution(LabeledTreeNode treeNode, int N) {
		double p_x_0;
		double p_x_1;
		int m_x_0;
		int m_x_1;
		double p_p;
		int m_p;
		double score;

		// compute the probability and frequency of the node x

		p_x_0 = treeNode.distribution[0];
		// m_i(x_0,l)
		m_x_0 = (int) (p_x_0 * N);
		p_x_1 = treeNode.distribution[1];
		// m_i(x_1,l)
		m_x_1 = (int) (p_x_1 * N);

		// is this node reachable? if not get the hell out of here

		if ((p_x_0 == 0.0d) && (p_x_1 == 0.0d))
			return Double.NEGATIVE_INFINITY;

		// alright, let's go for it, compute the probability and frequency of the
		// parents

		p_p = p_x_0 + p_x_1;
		// m_i(l)
		m_p = (int) (p_p * N);

		// compute basic contribution of this node - log BD score

		score = -metricUtil.logGamma(2 + m_p) + metricUtil.logGamma(1 + m_x_0)
				+ metricUtil.logGamma(1 + m_x_1);

		// return the score

		return score;
	}
}
